// OpentTxl-C Version 11 grammar compiler
// J.R. Cordy, Jan 2023

// Copyright 2023, James R. Cordy and others

// Permission is hereby granted, free of charge, to any person obtaining a copy of this software 
// and associated documentation files (the “Software”), to deal in the Software without restriction, 
// including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, 
// and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, 
// subject to the following conditions:

// The above copyright notice and this permission notice shall be included in all copies 
// or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE 
// AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

// Abstract

// The TXL grammar compiler.
// Compiles the grammar defines in the TXL program into a grammar tree which encodes the generic
// parse tree used by the parser to generate a parse tree for the input language input tokens.
// Takes as input the parsed TXL program as a parse tree according to the TXL bootstrap grammar
// and processes the contents of each parsed define statement. Builds a table of grammar trees
// for each defined symbol, and returns the grammar tree for the [program] symbol_

// Modification Log

// v11.0 Initial revision, adapted from OpenTxl 11.0

#define COMPILER

// I/O, strings, memory allocation
#include "support.h"

// Global modules
#include "limits.h"
#include "options.h"
#include "tokens.h"
#include "trees.h"
#include "shared.h"
#include "idents.h"
#include "symbols.h"
#include "errors.h"
#include "txltree.h"

// Check interface consistency
#include "compdef.h"

static void defineCompiler_processOpt (const tokenT XT, treePT *optTP)
{
    //  [opt X]   ==>   opt__X  where
    //  opt__X     -->   [X]   |   [empty]

    // First check to see if we've already done one of these
    string optXname;
    stringcpy (optXname, "opt__"), stringcat (optXname, *ident_idents[XT]);
    const tokenT optXtoken = ident_install (optXname, treeKind_id);
    int optIndex = symbol_lookupSymbol (optXtoken);

    if (optIndex != NOT_FOUND) {
        // We're in luck, one exists already, so share it!
        *optTP = symbol_symbols[optIndex];

    } else {
        // It's a new one, so build it
        const int Xindex = symbol_enterSymbol (XT, treeKind_undefined);  // [X] possibly not defined yet
        const treePT XTP = symbol_symbols[Xindex];

        optIndex = symbol_enterSymbol (optXtoken, treeKind_choose);
        *optTP = symbol_symbols[optIndex];

        tree_makeTwoKids (*optTP, XTP, emptyTP);
    }
}

static void defineCompiler_processAttribute (const tokenT XT, treePT *attrTP)
{
    //  [attr X]   ==>   attr__X  where
    //  attr__X    -->   [attr_1_X]   |   [empty]
    //  attr_1_X   -->   [ATTR] [X]

    // First check to see if we've already done one of these
    string attrXname;
    stringcpy (attrXname, "attr__"), stringcat (attrXname, *ident_idents[XT]);
    const tokenT attrXtoken = ident_install (attrXname, treeKind_id);
    int attrIndex = symbol_lookupSymbol (attrXtoken);

    if (attrIndex != NOT_FOUND) {
        // We're in luck, one exists already, so share it!
        *attrTP = symbol_symbols[attrIndex];

    } else {
        // It's a new one, so build it
        const int Xindex = symbol_enterSymbol (XT, treeKind_undefined);  // [X] possibly not defined yet
        const treePT XTP = symbol_symbols[Xindex];

        attrIndex = symbol_enterSymbol (attrXtoken, treeKind_choose);
        *attrTP = symbol_symbols[attrIndex];

        string attr1Xname;
        stringcpy (attr1Xname, "attr_1_"), stringcat (attr1Xname, *ident_idents[XT]);
        tokenT attr1XToken = ident_install (attr1Xname, treeKind_id);
        const int attr1XIndex = symbol_enterSymbol (attr1XToken, treeKind_order);
        const treePT attr1XTP = symbol_symbols[attr1XIndex];

        const int ATTRindex = symbol_lookupSymbol (ATTR_T);
        const treePT ATTR_TP = symbol_symbols[ATTRindex];

        tree_makeTwoKids (attr1XTP, ATTR_TP, XTP);
        tree_makeTwoKids (*attrTP, attr1XTP, emptyTP);
    }
}

static void defineCompiler_processLookahead (const tokenT XT, treePT *seeTP, const string seeNot)
{
    //  [see X]   ==>   [(look)see__X]  where
    //  (look)see__X  -->   [X]  |  [SEE]
    //  SEE           -->   [empty]
    
    // ( and similarly for [not X] )

    // First check to see if we've already done one of these
    string seeNotXname;
    stringcpy (seeNotXname, seeNot), stringcat (seeNotXname, "__"), stringcat (seeNotXname, *ident_idents[XT]);
    const tokenT seeXtoken = ident_install (seeNotXname, treeKind_id);
    int seeIndex = symbol_lookupSymbol (seeXtoken);

    if (seeIndex != NOT_FOUND) {
        // We're in luck, one exists already, so share it!
        *seeTP = symbol_symbols[seeIndex];

    } else {
        // It's a new one, so build it
        const int Xindex = symbol_enterSymbol (XT, treeKind_undefined);  // [X] possibly not defined yet
        const treePT XTP = symbol_symbols[Xindex];

        seeIndex = symbol_enterSymbol (seeXtoken, treeKind_lookahead);
        *seeTP = symbol_symbols[seeIndex];

        int SEEindex;
        if (stringcmp (seeNot, "see") == 0) {
            SEEindex = symbol_lookupSymbol (SEE_T);
        } else {
            SEEindex = symbol_lookupSymbol (NOT_T);
        };
        const treePT SEE_TP = symbol_symbols[SEEindex];

        tree_makeTwoKids (*seeTP, XTP, SEE_TP);
    }
}

static void defineCompiler_processPushPop (const tokenT XT, treePT *pushTP, const string pushPop)
{
    //  [push X]   ==>   [(push)push__X]  where
    //  (push)push__X  -->   [X] 
    
    // ( and similarly for [pop X] )

    // First check to see if we've already done one of these
    string pushXname;
    stringcpy (pushXname, pushPop), stringcat (pushXname, "__"), stringcat (pushXname, *ident_idents[XT]);
    const tokenT pushXtoken = ident_install (pushXname, treeKind_id);
    int pushIndex = symbol_lookupSymbol (pushXtoken);

    if (pushIndex != NOT_FOUND) {
        // We're in luck, one exists already, so share it!
        *pushTP = symbol_symbols[pushIndex];

    } else {
        // It's a new one, so build it
        const int Xindex = symbol_enterSymbol (XT, treeKind_undefined);  // [X] possibly not defined yet
        const treePT XTP = symbol_symbols[Xindex];

        if (stringcmp (pushPop, "push") == 0) {
            pushIndex = symbol_enterSymbol (pushXtoken, treeKind_push);
        } else {
            pushIndex = symbol_enterSymbol (pushXtoken, treeKind_pop);
        }

        *pushTP = symbol_symbols[pushIndex];

        tree_makeOneKid (*pushTP, XTP);
    }
}

static void defineCompiler_processRepeat (const tokenT XT, treePT *repeatTP, treePT *repeatFirstTP)
{
    //  [repeat X]   ==>   [(gen)repeat_0_X], where
    //     (gen)repeat_0_X   -->   [X]
    //  [repeat X+]  ==>   [repeat_1_X], where
    //     repeat_1_X   -->  [X] [(gen)repeat_0_X]

    // First check to see if we've already done one of these
    string repeatXname;
    stringcpy (repeatXname, "repeat_0_"), stringcat (repeatXname, *ident_idents[XT]);
    const tokenT repeatXtoken = ident_install (repeatXname, treeKind_id);
    int repeatIndex = symbol_lookupSymbol (repeatXtoken);

    if (repeatIndex != NOT_FOUND) {
        // We're in luck, one exists already, so share it!
        *repeatTP = symbol_symbols[repeatIndex];
        *repeatFirstTP = symbol_symbols[repeatIndex + 1];

    } else {
        // It's a new one, so build it
        const int Xindex = symbol_enterSymbol (XT, treeKind_undefined);  // [X] possibly not defined yet
        const treePT XTP = symbol_symbols[Xindex];

        repeatIndex = symbol_enterSymbol (repeatXtoken, treeKind_generaterepeat);
        *repeatTP = symbol_symbols[repeatIndex];
        tree_makeOneKid (*repeatTP, XTP);

        string repeat1Xname;
        stringcpy (repeat1Xname, "repeat_1_"), stringcat (repeat1Xname, *ident_idents[XT]);
        const tokenT repeatOneToken = ident_install (repeat1Xname, treeKind_id);
        const int repeatOneIndex = symbol_enterSymbol (repeatOneToken, treeKind_repeat);
        assert (repeatOneIndex == repeatIndex + 1);

        *repeatFirstTP = symbol_symbols[repeatOneIndex];
        tree_makeTwoKids (*repeatFirstTP, XTP, *repeatTP);
    }
}

static void defineCompiler_processList (const tokenT XT, treePT *listTP, treePT *listFirstTP)
{
    //  [list X]   ==>   [(gen)list_0_X], where
    //     (gen)list_0_X   -->   [X]
    //  [list X+]  ==>   [list_1_X], where
    //     list_1_X   -->  [X] [(gen)list_0_X]

    // First check to see if we've already done one of these
    string listXname;
    stringcpy (listXname, "list_0_"), stringcat (listXname, *ident_idents[XT]);
    const tokenT listXtoken = ident_install (listXname, treeKind_id);
    int listIndex = symbol_lookupSymbol (listXtoken);

    if (listIndex != NOT_FOUND) {
        // We're in luck, one exists already, so share it!
        *listTP = symbol_symbols[listIndex];
        *listFirstTP = symbol_symbols[listIndex + 1];

    } else {
        // It's a new one, so build it
        const int Xindex = symbol_enterSymbol (XT, treeKind_undefined);  // [X] possibly not defined yet
        const treePT XTP = symbol_symbols[Xindex];

        listIndex = symbol_enterSymbol (listXtoken, treeKind_generatelist);
        *listTP = symbol_symbols[listIndex];
        tree_makeOneKid (*listTP, XTP);

        string list1Xname;
        stringcpy (list1Xname, "list_1_"), stringcat (list1Xname, *ident_idents[XT]);
        const tokenT listOneToken = ident_install (list1Xname, treeKind_id);
        const int listOneIndex = symbol_enterSymbol (listOneToken, treeKind_list);
        assert (listOneIndex == listIndex + 1);

        *listFirstTP = symbol_symbols[listOneIndex];
        tree_makeTwoKids (*listFirstTP, XTP, *listTP);
    }
}

static tokenT defineCompiler_makeListRepeatOrOptTargetT (const treePT idOrLiteralTP)
{
    assert (stringcmp (*ident_idents[tree_trees[idOrLiteralTP].name], "TXL_idOrLiteral_") == 0);
    assert ((stringcmp (*ident_idents[tree_trees[tree_kid1TP (idOrLiteralTP)].name], "TXL_literal_") == 0)
        || (tree_trees[tree_kid1TP (idOrLiteralTP)].kind == treeKind_id));

    if (txltree_literalP (tree_kid1TP (idOrLiteralTP))) {
        // it's a literal, so make a phoney nonterminal for it
        assert (stringcmp (*ident_idents[tree_trees[tree_kid1TP (idOrLiteralTP)].name], "TXL_literal_") == 0);
        const tokenT terminalT = txltree_literal_tokenT (tree_kid1TP (idOrLiteralTP));
        const tokenT rawterminalT = txltree_literal_rawtokenT (tree_kid1TP (idOrLiteralTP));
        const treePT terminalTP = tree_newTreeInit (treeKind_literal, terminalT, rawterminalT, 0, nilKid);
        string terminal;
        stringcpy (terminal, *ident_idents[terminalT]);
        string litName;
        stringcpy (litName, "lit__"), stringcat (litName, terminal);
        const tokenT targetT = ident_install (litName, treeKind_id);
        const int targetIndex = symbol_enterSymbol (targetT, treeKind_order);
        const treePT targetTP = symbol_symbols[targetIndex];
        tree_makeOneKid (targetTP, terminalTP);
        return (targetT);

    } else {
        // it's a nonterminal id, so simply return it
        assert (tree_trees[tree_kid1TP (idOrLiteralTP)].kind == treeKind_id);
        const treePT idTP = tree_kid1TP (idOrLiteralTP);
        return (tree_trees[idTP].name);
    }
}

static void defineCompiler_processOneKid (const tokenT defineNameT, const treePT literalOrBracketedIdTP, treePT *kidTP)
{
    treePT      dummyTP;

    const treePT  literalOrBracketedId_kid1TP = tree_kid1TP (literalOrBracketedIdTP);

    if (txltree_literalP (literalOrBracketedId_kid1TP)) {
        // terminal
        const tokenT terminalT = txltree_literal_tokenT (literalOrBracketedId_kid1TP);
        const tokenT rawterminalT = txltree_literal_rawtokenT (literalOrBracketedId_kid1TP);
        *kidTP = tree_newTreeInit (treeKind_literal, terminalT, rawterminalT, 0, nilKid);
        const int terminalIndex = symbol_lookupSymbol (terminalT);

        if ((terminalIndex != NOT_FOUND) && (!txltree_isQuotedLiteral (literalOrBracketedId_kid1TP))) {
            string context, message;
            stringprintf (context, "define '%s'", *ident_idents[defineNameT]);
            stringprintf (message, "Type name '%s' used as a literal identifier (use [%s] or '%s instead)",
                *ident_idents[terminalT], *ident_idents[terminalT], *ident_idents[terminalT]);
            error (context, message, WARNING, 201);
        }

    } else if (txltree_listP (literalOrBracketedId_kid1TP)) {
        // [list X]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processList (XT, kidTP, &(dummyTP));

    } else if (txltree_list1P (literalOrBracketedId_kid1TP)) {
        // [list X+]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processList (XT, &(dummyTP), kidTP);

    } else if (txltree_repeatP (literalOrBracketedId_kid1TP)) {
        // [repeat X]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processRepeat (XT, kidTP, &(dummyTP));

    } else if (txltree_repeat1P (literalOrBracketedId_kid1TP)) {
        // [repeat X+]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processRepeat (XT, &(dummyTP), kidTP);

    } else if (txltree_optP (literalOrBracketedId_kid1TP)) {
        // [opt X]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processOpt (XT, kidTP);

    } else if (txltree_attrP (literalOrBracketedId_kid1TP)) {
        // [attr X]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processAttribute (XT, kidTP);

    } else if (txltree_seeP (literalOrBracketedId_kid1TP)) {
        // [see X]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processLookahead (XT, kidTP, "see");

    } else if (txltree_notP (literalOrBracketedId_kid1TP)) {
        // [not X]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processLookahead (XT, kidTP, "not");

    } else if (txltree_fenceP (literalOrBracketedId_kid1TP)) {
        // [!]
        const int FENCEindex = symbol_lookupSymbol (FENCE_T);
        *kidTP = symbol_symbols[FENCEindex];

    } else if (txltree_pushP (literalOrBracketedId_kid1TP)) {
        // [push X]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processPushPop (XT, kidTP, "push");

    } else if (txltree_popP (literalOrBracketedId_kid1TP)) {
        // [pop X]
        const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (literalOrBracketedId_kid1TP);
        const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
        defineCompiler_processPushPop (XT, kidTP, "pop");

    } else if (txltree_bracketedDescriptionP (literalOrBracketedId_kid1TP)) {
        // [X]
        const tokenT XT = txltree_bracketedDescription_idT (literalOrBracketedId_kid1TP);
        const int kidIndex = symbol_enterSymbol (XT, treeKind_undefined);  // possibly not yet defined
        *kidTP = symbol_symbols[kidIndex];

    } else {
        string context;
        stringprintf (context, "define '%s'", *ident_idents[defineNameT]);
        error (context, "Fatal TXL error in processOneKid", INTERNAL_FATAL, 202);
    }
}

static void defineCompiler_processKids (const tokenT defineNameT, const treePT kidsTP, const int parentIndex, const bool extension)
{
    assert (!(tree_plural_emptyP (kidsTP)));

    const treePT parentTP = symbol_symbols[parentIndex];

    // allocate kids contiguously - necessary for high-falutin' parser speedups!
    treePT kidsToCountTP = kidsTP;
    int nkids = 1;
    while (true) {
        kidsToCountTP = tree_plural_restTP (kidsToCountTP);
        if (tree_plural_emptyP (kidsToCountTP)) break;
        nkids += 1;
    }

    // if this is an extension, then we already have one kid
    if (extension) {
        nkids += tree_trees[parentTP].count;
    }

    if (nkids > maxDefineKids) {
        string context, message;
        stringprintf (context, "define '%s'", *ident_idents[defineNameT]);
        stringprintf (message, "Too many elements or alternatives in one define (maximum %d)", maxDefineKids);
        error (context, message, LIMIT_FATAL, 203);
    }

    kidPT kidListKP = tree_newKids (nkids);
    const kidPT saveKidListKP = kidListKP;

    int firstKid = 1;

    if (extension) {
        // install the existing kids
        kidPT oldKidListKP = tree_trees[parentTP].kidsKP;
        for (int kid = 1; kid <= tree_trees[parentTP].count; kid++) {
            tree_setKidTree (kidListKP, tree_kids[oldKidListKP]);
            oldKidListKP += 1;
            kidListKP += 1;
            firstKid += 1;
        }
    }

    tree_setKids (parentTP, saveKidListKP);
    tree_setCount (parentTP, nkids);

    // Now fill them in
    treePT kidsLeftToProcessTP = kidsTP;
    for (int kid = firstKid; kid <= nkids; kid++) {
        treePT literalOrBracketedIdTP = tree_plural_firstTP (kidsLeftToProcessTP);

        treePT kidTP;
        defineCompiler_processOneKid (defineNameT, literalOrBracketedIdTP, &(kidTP));
        tree_setKidTree (kidListKP, kidTP);

        kidsLeftToProcessTP = tree_plural_restTP (kidsLeftToProcessTP);
        kidListKP += 1;
    }
}

static void defineCompiler_checkUserDefinedName (const tokenT name)
{
    if ((stringncmp (*ident_idents[name], "list_", 5) == 0) 
            || (stringncmp (*ident_idents[name], "repeat_", 7) == 0) 
            || (stringncmp (*ident_idents[name], "opt_", 4) == 0) 
            || (stringncmp (*ident_idents[name], "attr_", 5) == 0) 
            || (stringncmp (*ident_idents[name], "lit_", 4) == 0) 
            || (stringncmp (*ident_idents[name], "push_", 5) == 0) 
            || (stringncmp (*ident_idents[name], "pop_", 4) == 0) 
            || (stringncmp (*ident_idents[name], "TXL_", 4) == 0)) {
        string context;
        stringprintf (context, "define '%s'", *ident_idents[name]);
        error (context, "'list_', 'repeat_', 'opt_', 'attr_', 'lit_', 'push_', 'pop_' and 'TXL_' name prefixes are reserved for TXL internal use", FATAL, 204);
    }
}

static tokenT defineCompiler_generateNewName (const tokenT nameT)
{
    // Generate an illegal name so user can't use it
    //     >>--  Leading underscores are not legal
    string baseName;
    stringcpy (baseName, *ident_idents[nameT]);
    string newName;
    for (int i = 1; i <= 1000; i++) {
        stringprintf (newName, "__%s_%d__", baseName, i);
        if (ident_lookup (newName) == NOT_FOUND) break;
    }
    return (ident_install (newName, treeKind_id));
}

static void defineCompiler_processDefine (const treePT defineTP)
{
    const tokenT defineOrRedefineT = txltree_define_defineOrRedefineT (defineTP);
    const tokenT defineNameT = txltree_define_nameT (defineTP);
    const treePT optPreDotDotDot = txltree_define_optDotDotDotBarTP (defineTP);
    const treePT literalsAndBracketedIds = txltree_define_literalsAndBracketedIdsTP (defineTP);
    const treePT barOrders = txltree_define_barOrdersTP (defineTP);
    const treePT optPostDotDotDot = txltree_define_optBarDotDotDotTP (defineTP);

    defineCompiler_checkUserDefinedName (defineNameT);

    const int symbolIndex = symbol_enterSymbol (defineNameT, treeKind_undefined);

    const bool preextension = !tree_plural_emptyP (optPreDotDotDot);
    const bool postextension = !tree_plural_emptyP (optPostDotDotDot);
    const bool extension = preextension || postextension;

    bool chooseExtension = false;
    if (preextension) {
        chooseExtension = !tree_plural_emptyP (tree_kid2TP (tree_kid1TP (optPreDotDotDot)));
    } else if (postextension) {
        chooseExtension = !tree_plural_emptyP (tree_kid1TP (tree_kid1TP (optPostDotDotDot)));
    }

    // We have a problem if we have both pre- and post- extensions
    if (preextension && postextension) {
        string context;
        stringprintf (context, "define '%s'", *ident_idents[defineNameT]);
        error (context, "Defines cannot be both pre- and post-extended in the same definition (split into two redefines)", FATAL, 212);
    }

    if (tree_trees[symbol_symbols[symbolIndex]].kind != treeKind_undefined) {

        if (tree_trees[symbol_symbols[symbolIndex]].kind > treeKind_literal) {
            // override of a token - bad news!
            string context, message;
            stringprintf (context, "define '%s'", *ident_idents[defineNameT]);
            stringprintf (message, "Define overrides token definition for [%s]", *ident_idents[defineNameT]);
            error (context, message, FATAL, 205);

        } else {
            if (extension) {
                // A new-style extended define; it can be one of four cases
                //      ... | [X]       add new post-alternatives
                //      [X] | ...       add new pre-alternatives
                //      ... [X]         add new tail
                //      [X] ...         add new head

                if (chooseExtension) {
                    // make sure it is a choose
                    if (tree_trees[symbol_symbols[symbolIndex]].kind == treeKind_order) {
                        // Make it a new one-kid choose with the previous order as the one kid
                        const tokenT newNameT = defineCompiler_generateNewName (defineNameT);
                        const int newSymIndex = symbol_enterSymbol (newNameT, treeKind_undefined);
                        tree_cloneTree (symbol_symbols[newSymIndex], symbol_symbols[symbolIndex]);
                        tree_setName (symbol_symbols[newSymIndex], newNameT);
                        tree_setRawName (symbol_symbols[newSymIndex], newNameT);
                        // now it's a choose with its former order self as kid
                        tree_setKind (symbol_symbols[symbolIndex], treeKind_choose);
                        tree_makeOneKid (symbol_symbols[symbolIndex], symbol_symbols[newSymIndex]);
                    }
                } else {
                    // make sure it is an order
                    if (tree_trees[symbol_symbols[symbolIndex]].kind == treeKind_choose) {
                        // Make it a new one-kid order with the previous definition as the one kid
                        const tokenT newNameT = defineCompiler_generateNewName (defineNameT);
                        const int newSymIndex = symbol_enterSymbol (newNameT, treeKind_undefined);
                        tree_cloneTree (symbol_symbols[newSymIndex], symbol_symbols[symbolIndex]);
                        tree_setName (symbol_symbols[newSymIndex], newNameT);
                        tree_setRawName (symbol_symbols[newSymIndex], newNameT);
                        // now it's an order with its former choose self as kid
                        tree_setKind (symbol_symbols[symbolIndex], treeKind_order);
                        tree_makeOneKid (symbol_symbols[symbolIndex], symbol_symbols[newSymIndex]);
                    }
                }

            } else {
                if (defineOrRedefineT != redefine_T) {
                    string context;
                    stringprintf (context, "define '%s'", *ident_idents[defineNameT]);
                    error (context, "Define overrides previous declaration ('redefine' should be used if override intended)", WARNING, 206);
                }
            }
        }

    } else {
        if (extension) {
            string context, message;
            stringprintf (context, "define/redefine '%s'", *ident_idents[defineNameT]);
            stringprintf (message, "Extended define '%s' has not been previously defined",*ident_idents[defineNameT]);
            error (context, message, FATAL, 207);
        }
    }

    // Empty defines mus be explicit
    if (tree_plural_emptyP (literalsAndBracketedIds)) {
        string context;
        stringprintf (context, "define '%s'", *ident_idents[defineNameT]);
        error (context, "Empty defines not allowed - use [empty] instead", FATAL, 208);
    }

    if (tree_plural_emptyP (barOrders) && (!chooseExtension)) {
        if (!extension) {
            // a new define
            tree_setKind (symbol_symbols[symbolIndex], treeKind_order);
        }

        int nOldKids;

        if (extension) {
            // Preserve the existing kids in the new set of alternatives
            nOldKids = tree_trees[symbol_symbols[symbolIndex]].count;
        }

        defineCompiler_processKids (defineNameT, literalsAndBracketedIds, symbolIndex, extension);

        if (postextension) {
            assert (!preextension);
            // Move the original kids to the end of the alternatives
            // e.g., [old1] [old2] [new1] [new2] => [new1] [new2] [old1] [old2]
            const kidPT kidBase = tree_trees[symbol_symbols[symbolIndex]].kidsKP;
            const int nkids = tree_trees[symbol_symbols[symbolIndex]].count;
            for (int k = 1; k <= nOldKids; k++) {
                // Rotate the kids
                const treePT firstKid = tree_kids[kidBase];
                for (int i = 1; i <= nkids -1; i++) {
                    tree_setKidTree ((kidBase + i) - 1, tree_kids[kidBase + i]);
                }
                tree_setKidTree ((kidBase + nkids) - 1, firstKid);
            }
        }

    } else {
        if (!extension) {
            // A new define
            tree_setKind (symbol_symbols[symbolIndex], treeKind_choose);
            tree_setKids (symbol_symbols[symbolIndex], nilKid);
        }

        // Allocate the kids contiguously - necessary for high-falutin' parser speedups!
        treePT kidsToCountTP = barOrders;
        int nkids = 1;

        if (extension) {
            // Don't forget the previous kids!
            nkids += tree_trees[symbol_symbols[symbolIndex]].count;
        }

        while (true) {
            if (tree_plural_emptyP (kidsToCountTP)) break;
            nkids += 1;
            kidsToCountTP = tree_kid3TP (tree_kid1TP (kidsToCountTP));
        }

        if (nkids > maxDefineKids) {
            string context, message;
            stringprintf (context, "define/redefine '%s'", *ident_idents[defineNameT]);
            stringprintf (message, "Too many elements or alternatives in one define (maximum %d)", maxDefineKids);
            error (context, message, LIMIT_FATAL, 210);
        }

        kidPT kidListKP = tree_newKids (nkids);

        int nextKid = 1;
        int nOldKids = 0;

        if (extension) {
            // Preserve the existing kids in the new set of alternatives
            nOldKids = tree_trees[symbol_symbols[symbolIndex]].count;
            for (int k = 0; k <= nOldKids - 1; k++) {
                tree_setKidTree (kidListKP + k, tree_kids[tree_trees[symbol_symbols[symbolIndex]].kidsKP + k]);
            }

            tree_setKids (symbol_symbols[symbolIndex], kidListKP);
            tree_setCount (symbol_symbols[symbolIndex], nkids);

            kidListKP += nOldKids;
            nextKid += nOldKids;

        } else {
            // Begin a new set of alternative kids
            tree_setKids (symbol_symbols[symbolIndex], kidListKP);
            tree_setCount (symbol_symbols[symbolIndex], nkids);
        }

        // Have to handle the first alternative specially since it parses slightly differently

        if (tree_plural_emptyP (tree_plural_restTP (literalsAndBracketedIds))) {
            // A single element first alternative, e.g., [X], [opt X], [repeat X], ... 
            treePT kidTP;
            defineCompiler_processOneKid (defineNameT, tree_plural_firstTP (literalsAndBracketedIds), &(kidTP));
            tree_setKidTree (kidListKP, kidTP);

        } else {
            // A multiple element first alternative, e.g., [X] [Y] [Z]
            // Generate a new name for this first alternative, and enter it into the symbol table
            const tokenT newNameT = defineCompiler_generateNewName (defineNameT);
            // It's an ordered sequence of elements
            const int newSymIndex = symbol_enterSymbol (newNameT, treeKind_order);
            defineCompiler_processKids (defineNameT, literalsAndBracketedIds, newSymIndex, false);
            tree_setKidTree (kidListKP, (symbol_symbols[newSymIndex]));
        }

        kidListKP += 1;
        nextKid += 1;

        treePT nextBarOrders = barOrders;

        for (int barOrder = nextKid; barOrder <= nkids; barOrder++) {
            // LAndBIds == LiteralsAndBracketedIds
            treePT nextLAndBIdsTP = tree_kid2TP (tree_kid1TP (nextBarOrders));

            if (tree_plural_emptyP (nextLAndBIdsTP)) {
                string context;
                stringprintf (context, "define '%s'", *ident_idents[defineNameT]);
                error (context, "Empty alternatives not allowed - use [empty] instead", FATAL, 209);
            }

            if (tree_plural_emptyP (tree_plural_restTP (nextLAndBIdsTP))) {
                // A single element alternative, e.g., [X], [opt X], [repeat X], ... 
                treePT  kidTP;
                defineCompiler_processOneKid (defineNameT, tree_plural_firstTP (nextLAndBIdsTP), &(kidTP));
                tree_setKidTree (kidListKP, kidTP);

            } else {
                // A multiple element first alternative, e.g., [X] [Y] [Z]
                // Generate a new name for this first alternative, and enter it into the symbol table
                const tokenT newNameT = defineCompiler_generateNewName (defineNameT);
                // It's an ordered sequence of elements
                const int newSymIndex = symbol_enterSymbol (newNameT, treeKind_order);
                defineCompiler_processKids (defineNameT, nextLAndBIdsTP, newSymIndex, false);
                tree_setKidTree (kidListKP, symbol_symbols[newSymIndex]);
            }

            nextBarOrders = tree_kid3TP (tree_kid1TP (nextBarOrders));
            kidListKP += 1;
        }

        assert (tree_plural_emptyP (nextBarOrders));

        if (postextension) {
            assert (!preextension);
            // Move the original kids to the end of the alternatives
            // e.g., [old1] | [old2] | [new1] | [new2] => [new1] | [new2] | [old1] | [old2]
            const kidPT kidBase = tree_trees[symbol_symbols[symbolIndex]].kidsKP;
            for (int k = 1; k <= nOldKids; k++) {
                // Rotate the kids
                const treePT firstKid = tree_kids[kidBase];
                for (int i = 1; i <= nkids -1; i++) {
                    // (i-1)th kid = (i)th kid;
                    tree_setKidTree ((kidBase + i) - 1, tree_kids[kidBase + i]);
                }
                tree_setKidTree ((kidBase + nkids) - 1, firstKid);
            }
        }
    }
}

static bool defineCompiler_isLeftRecursiveDefine (const treePT defineTP)
{
    // Check to see if a define is directly left recursive
    // Example :
    //   define expression
    //          [term]
    //      |   [expression1] 
    //   end define
    //
    //   define expression1
    //          [expression] + [term]
    //   end define

    if (tree_trees[defineTP].kind == treeKind_choose) {
        // Because of overrides, we may end up with a family of names for the same nonterminal definition
        string originalDefineName;
        externalType (*ident_idents[tree_trees[defineTP].name], originalDefineName);

        // Check each alternative to see if it begins with a recursive reference
        const kidPT baseKid = (tree_trees[defineTP].kidsKP) - 1;
        const int nkids = tree_trees[defineTP].count;

        for (int kid = 1; kid <= nkids; kid++) {
            // Is the first thing in this alternative a recursive reference?
            const treePT defineKidTP = tree_kids[baseKid + kid];

            if (tree_trees[defineKidTP].kind == treeKind_order) {
                // We must compare by original name in case it has been renamed by an override
                string defineKidFirstRefName;
                externalType (*ident_idents[tree_trees[tree_kids[tree_trees[defineKidTP].kidsKP]].name], defineKidFirstRefName);

                if (stringcmp (defineKidFirstRefName, originalDefineName) == 0) {
                    // Yes, it's left recursive
                    return (true);
                }
            }
        }
    }

    // Nope, it's not left recursive
    return (false);
}

static void defineCompiler_refactorLeftRecursiveDefine (const treePT defineTP)
{
    assert (defineCompiler_isLeftRecursiveDefine (defineTP));

    // Change to left factored choice, so that the parser can build the original grammar's parse tree
    assert (tree_trees[defineTP].kind == treeKind_choose);
    tree_setKind (defineTP, treeKind_leftchoose);

    // Step 1. Sort alternatives to all non-recursives followed by all recursives 
    const kidPT baseKid = (tree_trees[defineTP].kidsKP) - 1;
    const int nkids = tree_trees[defineTP].count;
    int lastNonRecursiveKid = 0;

    // Bubble sort non-recursive alternativess before recursive alternatives
    for (int kid = 1; kid <= nkids; kid ++) {
        treePT kidDefineTP = tree_kids[baseKid + kid];

        // Each non-recursive alternative
        if ((tree_trees[kidDefineTP].kind != treeKind_order) || (tree_kids[tree_trees[kidDefineTP].kidsKP] != defineTP)) {

            // Bubble sort (to preserve order precedence) before recursive alternatives
            for (int k = kid; k >= 1; k--) {  // (sic)
                lastNonRecursiveKid = k;

                if (k == 1) break;

                const treePT kDefineTP = tree_kids[baseKid + k - 1];

                // Done when we hit a non-recursive alternative
                if ((tree_trees[kDefineTP].kind != treeKind_order) || (tree_kids[tree_trees[kDefineTP].kidsKP] != defineTP)) 
                    break;
                const kidPT thisKid = tree_kids[baseKid + k];
                tree_setKidTree (baseKid + k, tree_kids[baseKid + k - 1]);
                tree_setKidTree (baseKid + k - 1, thisKid);
            }
        }
    }

    // Step 2. Factor recursive and nonrecursive cases into subchoices 
    if (options_option[verbose_p]) {
        string context;
        stringprintf (context, "define '%s'", *ident_idents[tree_trees[defineTP].name]);
        error (context, "Optimized left recursive define", INFORMATION, 213);
    }

    // Convert E -> T | E + T to left-factored form  
    //  E -> E1 | E E2
    //  E1 -> T
    //  E2 -> + T

    // Number of non-recursive and recursive alternatives
    const int nNonRecursiveKids = lastNonRecursiveKid;
    const int nRecursiveKids = nkids - lastNonRecursiveKid;

    // First non-recursive and recursive alternatives
    const kidPT nonRecursiveKidsKP = baseKid + 1;
    const kidPT recursiveKidsKP = (baseKid + lastNonRecursiveKid) + 1;

    // Build the new define for E, with two alternatives, non-recursive (E1) and recursive (E E2)
    const kidPT newDefineKidsKP = tree_newKids (2);
    tree_setCount (defineTP, 2);
    tree_setKids (defineTP, newDefineKidsKP);

    // Build a define for E1 with all non-recursive alternatives, and enter it as first alternative of the new E
    if (nNonRecursiveKids > 1) {
        // Build a define for E1
        const tokenT E1nameT = defineCompiler_generateNewName (tree_trees[defineTP].name);
        const int E1index = symbol_enterSymbol (E1nameT, treeKind_choose);
        tree_setCount (symbol_symbols[E1index], nNonRecursiveKids);
        tree_setKids  (symbol_symbols[E1index], nonRecursiveKidsKP);

        // Make an order node to reference E1
        const tokenT orderNameT = defineCompiler_generateNewName (tree_trees[defineTP].name);
        const int orderIndex = symbol_enterSymbol (orderNameT, treeKind_order);
        tree_setCount (symbol_symbols[orderIndex], 1);

        // Make it the first alternative of the new E
        const kidPT newKid = tree_newKid ();
        tree_setKids (symbol_symbols[orderIndex], newKid);
        tree_setKidTree (tree_trees[symbol_symbols[orderIndex]].kidsKP, symbol_symbols[E1index]);
        tree_setKidTree (newDefineKidsKP, symbol_symbols[orderIndex]);

    } else {
        // Of course, if there is only one non-recursive alternative, it already is E1, 
        // so just make it the first alternative of the new E
        tree_setKidTree (newDefineKidsKP, tree_kids[nonRecursiveKidsKP]);
    }

    // Build a define for E2 with all recursive alternatives
    const tokenT E2nameT = defineCompiler_generateNewName (tree_trees[defineTP].name);
    const int E2index = symbol_enterSymbol (E2nameT, treeKind_choose);
    tree_setCount (symbol_symbols[E2index], nRecursiveKids);
    tree_setKids  (symbol_symbols[E2index], recursiveKidsKP);

    // Modify each recursive alternative to skip the recursive reference but preserve the tail
    for (int k = recursiveKidsKP; k <= recursiveKidsKP + nRecursiveKids - 1; k++) {
        // Disconnect the alternative from its original nonterminal type in the symbol table,
        // since we're going to change it
        const treePT newKidTP = tree_newTreeClone (tree_kids[k]);
        tree_setKidTree (k, newKidTP);

        // Skip the first (recursive) element of the alternative, to leave the tail (e.g., E + T => + T)
        assert (tree_trees[tree_kids[k]].kind == treeKind_order);
        tree_setKids (tree_kids[k], (tree_trees[tree_kids[k]].kidsKP) + 1);
        tree_setCount (tree_kids[k], (tree_trees[tree_kids[k]].count) - 1);

        // If there was no tail on it, it was a circular recursion!
        if (tree_trees[tree_kids[k]].count == 0) {
            string context;
            stringprintf (context, "define '%s'", *ident_idents[tree_trees[defineTP].name]);
            error (context, "Definition is circular", FATAL, 214);
        }
    }

    // Build an order node for E E2 
    const tokenT orderNameT = defineCompiler_generateNewName (tree_trees[defineTP].name);
    const int orderIndex = symbol_enterSymbol (orderNameT, treeKind_order);
    tree_makeTwoKids (symbol_symbols[orderIndex], defineTP, symbol_symbols[E2index]);

    // Enter it as the second alternative for the new E
    tree_setKidTree (newDefineKidsKP + 1, symbol_symbols[orderIndex]);

    // After tne optimization, the parse structure for a recursive alternative E -> A (E + T)
    // has been redefined to E -> A (E1 E2 (+ T)), so we must change the definition of nonterminal A 
    // to match for consistency (otherwise, for example, patterns targeted at A will fail, 
    // and other references to A will get a different parse)

    for (int k = 1; k <= nRecursiveKids; k++) {
        // We have to do this manually since copyTree will go too deep!
        
        // First the (+ T) structure - its name is presently A
        const treePT AplusTTP = tree_kids[recursiveKidsKP + k - 1];
        const treePT AplusTcopyTP = tree_newTreeClone (AplusTTP);  // we can share the kids here without worry, so no tree copy

        // Now build the selected E2 (+ T) structure, which is a choose with one choice
        const treePT AE2TP = tree_newTreeClone (symbol_symbols[E2index]);
        tree_makeOneKid (AE2TP, AplusTcopyTP);

        // Now the E1 E2 structure, which is an order
        const treePT AE1E2TP = tree_newTreeClone (symbol_symbols[orderIndex]);
        tree_makeTwoKids (AE1E2TP, tree_kids[tree_trees[symbol_symbols[orderIndex]].kidsKP], AE2TP);

        // Fix the names in the structure to the ones the parser will use at parse time
        // WARNING - this must be completely consistent with parse.ch!
        
        // Use redundancy of rawname to swap names without a temporary
        tree_setName (AE1E2TP, tree_trees[AplusTcopyTP].rawname);
        tree_setName (AplusTcopyTP, tree_trees[AE1E2TP].rawname);
        tree_setRawName (AE1E2TP, tree_trees[AE1E2TP].name);
        tree_setRawName (AplusTcopyTP, tree_trees[AplusTcopyTP].name);

        // Find the left recursive form's original symbol table entry
        const int Aindex = symbol_lookupSymbol (tree_trees[AplusTTP].name);
        assert (Aindex != NOT_FOUND);

        // Update rather than replace it, to make sure that all other uses
        // linked to it in the grammar are updated
        tree_cloneTree (symbol_symbols[Aindex], AE1E2TP);
    }
}

static void defineCompiler_processImplicitType (const tokenT typeT, const treePT bracketedDescriptionTP)
{
    const int typeIndex = symbol_lookupSymbol (typeT);

    if (typeIndex == NOT_FOUND) {
        // must create a grammatical form for the constructed type if it is a repeat, list or opt
        treePT dummyTP1, dummyTP2;

        if (txltree_listP (bracketedDescriptionTP) || txltree_list1P (bracketedDescriptionTP)) {
            const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (bracketedDescriptionTP);
            const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
            defineCompiler_processList (XT, &(dummyTP1), &(dummyTP2));
        } else if (txltree_repeatP (bracketedDescriptionTP) || txltree_repeat1P (bracketedDescriptionTP)) {
            const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (bracketedDescriptionTP);
            const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
            defineCompiler_processRepeat (XT, &(dummyTP1), &(dummyTP2));
        } else if (txltree_optP (bracketedDescriptionTP)) {
            const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (bracketedDescriptionTP);
            const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
            defineCompiler_processOpt (XT, &(dummyTP1));
        } else if (txltree_attrP (bracketedDescriptionTP)) {
            const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (bracketedDescriptionTP);
            const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
            defineCompiler_processAttribute (XT, &(dummyTP1));
        } else if (txltree_seeP (bracketedDescriptionTP)) {
            const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (bracketedDescriptionTP);
            const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
            defineCompiler_processLookahead (XT, &(dummyTP1), "see");
        } else if (txltree_notP (bracketedDescriptionTP)) {
            const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (bracketedDescriptionTP);
            const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
            defineCompiler_processLookahead (XT, &(dummyTP1), "not");
        } else if (txltree_pushP (bracketedDescriptionTP)) {
            const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (bracketedDescriptionTP);
            const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
            defineCompiler_processPushPop (XT, &(dummyTP1), "push");
        } else if (txltree_popP (bracketedDescriptionTP)) {
            const treePT XTP = txltree_bracketedDescription_listRepeatOrOptTargetTP (bracketedDescriptionTP);
            const tokenT XT = defineCompiler_makeListRepeatOrOptTargetT (XTP);
            defineCompiler_processPushPop (XT, &(dummyTP1), "pop");
        }
    }
}

static void defineCompiler_processRuleImplicitTypes (const treePT ruleTP)
{
    // make sure each constructed nonterminal is defined,
    // in case it doesn't appear in the grammar
    // (e.g. construct X [repeat blortz] )

    // TXL 11.1, optional match/replace part 
    if (!tree_plural_emptyP (txltree_rule_optReplaceOrMatchPartTP (ruleTP))) {
        const tokenT ruleTargetT = txltree_rule_targetT (ruleTP);
        const treePT targetBracketedDescriptionTP = txltree_rule_targetBracketedDescriptionTP (ruleTP);
        defineCompiler_processImplicitType (ruleTargetT, targetBracketedDescriptionTP);
    }

    // Formal parameter types
    treePT formalsTP = txltree_rule_formalsTP (ruleTP);
    while (true) {
        if (tree_plural_emptyP (formalsTP)) break;
        const tokenT formalTargetT = txltree_formal_typeT (tree_plural_firstTP (formalsTP));
        const treePT bracketedDescriptionTP = txltree_formal_bracketedDescriptionTP (tree_plural_firstTP (formalsTP));
        defineCompiler_processImplicitType (formalTargetT, bracketedDescriptionTP);
        formalsTP = tree_plural_restTP (formalsTP);
    }

    // Prepattern types
    treePT prePatternTP = txltree_rule_prePatternTP (ruleTP);
    while (true) {
        if (tree_plural_emptyP (prePatternTP)) break;

        const treePT partTP = tree_kid1TP (tree_kid1TP (tree_kid1TP (prePatternTP)));

        if (stringcmp (*ident_idents[tree_trees[partTP].name], "TXL_constructPart_") == 0) {
            const tokenT constructTargetT = txltree_construct_targetT (partTP);
            const treePT bracketedDescriptionTP = txltree_construct_bracketedDescriptionTP (partTP);
            defineCompiler_processImplicitType (constructTargetT, bracketedDescriptionTP);
        } else if ((stringcmp (*ident_idents[tree_trees[partTP].name], "TXL_exportPart_") == 0) 
                || (stringcmp (*ident_idents[tree_trees[partTP].name], "TXL_importPart_") == 0)) {
            const tokenT importExportTargetT = txltree_import_export_targetT (partTP);
            if (importExportTargetT != NOT_FOUND) {
                const treePT bracketedDescriptionTP = txltree_import_export_bracketedDescriptionTP (partTP);
                defineCompiler_processImplicitType (importExportTargetT, bracketedDescriptionTP);
            }
        }
        prePatternTP = tree_plural_restTP (prePatternTP);
    }

    // Postpattern types
    treePT postPatternTP = txltree_rule_postPatternTP (ruleTP);
    while (true) {
        if (tree_plural_emptyP (postPatternTP)) break;
        const treePT partTP = tree_kid1TP (tree_kid1TP (tree_kid1TP (postPatternTP)));
        if (stringcmp (*ident_idents[tree_trees[partTP].name], "TXL_constructPart_") == 0) {
            const tokenT constructTargetT = txltree_construct_targetT (partTP);
            const treePT bracketedDescriptionTP = txltree_construct_bracketedDescriptionTP (partTP);
            defineCompiler_processImplicitType (constructTargetT, bracketedDescriptionTP);
        } else if ((stringcmp (*ident_idents[tree_trees[partTP].name], "TXL_exportPart_") == 0) 
                || (stringcmp (*ident_idents[tree_trees[partTP].name], "TXL_importPart_") == 0)) {
            const tokenT importExportTargetT = txltree_import_export_targetT (partTP);
            if (importExportTargetT != NOT_FOUND) {
                const treePT bracketedDescriptionTP = txltree_import_export_bracketedDescriptionTP (partTP);
                defineCompiler_processImplicitType (importExportTargetT, bracketedDescriptionTP);
            }
        }
        postPatternTP = tree_plural_restTP (postPatternTP);
    }
}

static void defineCompiler_setUpBuiltins (void) {
    // Enter all of TXL's predefined nonterminals in the grammar symbol table
    int symbolIndex;
    
    // [stringlit], e.g., "foo"
    symbolIndex = symbol_enterSymbol (stringlit_T, treeKind_stringlit);

    // [charlit], e.g., 'foo'
    symbolIndex = symbol_enterSymbol (charlit_T, treeKind_charlit);

    // [number], e.g. 42, 5.0, 2.4e-3
    symbolIndex = symbol_enterSymbol (number_T, treeKind_number);

    // [floatnumber], [decimalnumber] and [integernumber] are specializations of [number]
    // that constrain particular [number] tokens in the grammar when parsing input,
    // but yield [number] as the parsed result 

    // [floatnumber], e.g. 2.4e-3
    symbolIndex = symbol_enterSymbol (floatnumber_T, treeKind_floatnumber);

    // [decimalnumber], e.g. 2.4
    symbolIndex = symbol_enterSymbol (decimalnumber_T, treeKind_decimalnumber);

    // [integernumber], e.g., 42
    symbolIndex = symbol_enterSymbol (integernumber_T, treeKind_integernumber);

    // [id]
    symbolIndex = symbol_enterSymbol (id_T, treeKind_id);

    // [upperlowerid], [upperid], [lowerupperid]  and [lowerid] are specializations of [id]
    // that constrain particular [id] tokens in the grammar when parsing input,
    // but yield [id] as the parsed result 

    // [upperlowerid]
    symbolIndex = symbol_enterSymbol (upperlowerid_T, treeKind_upperlowerid);

    // [upperid]
    symbolIndex = symbol_enterSymbol (upperid_T, treeKind_upperid);

    // [lowerupperid]
    symbolIndex = symbol_enterSymbol (lowerupperid_T, treeKind_lowerupperid);

    // [lowerid]
    symbolIndex = symbol_enterSymbol (lowerid_T, treeKind_lowerid);

    // [srclinenumber] and [srcfilename] are specializations of [empty]
    // that store the original input source coordinates in the parse tree

    // [srclinenumber]
    symbolIndex = symbol_enterSymbol (srclinenumber_T, treeKind_srclinenumber);

    // [srcfilename]
    symbolIndex = symbol_enterSymbol (srcfilename_T, treeKind_srcfilename);

    // [token] is a generalization of all input token nonterminals that accepts any kind
    // of input token ([id], [number], [stringlit], ...) that is not a defined keyword
    // in the grammar but yields the actual input token nonterminal as the parsed result

    // [token]
    symbolIndex = symbol_enterSymbol (token_T, treeKind_token);

    // [key], any grammar defined keyword
    symbolIndex = symbol_enterSymbol (key_T, treeKind_key);

    // [comment], any grammar defined comment 
    symbolIndex = symbol_enterSymbol (comment_T, treeKind_comment);

    // [empty], always matches 
    symbolIndex = symbol_enterSymbol (empty_T, treeKind_empty);

    // [space] and [newline] are only used in character input mode, -char

    // [space], any default or user defined blank space character
    symbolIndex = symbol_enterSymbol (space_T, treeKind_space);

    // [newline], any default or user defined new line character
    symbolIndex = symbol_enterSymbol (newline_T, treeKind_newline);

    // User-defined tokens of the "tokens" section of the language grammar
    for (int k = firstUserTokenKind; k <= lastUserTokenKind; k++) {
        if (kindType[k] == undefined_T) break;
        symbolIndex = symbol_enterSymbol (kindType[k], (enum treeKindT) k);
    }

    // Output formatting hints [NL], [FL], [IN], [EX], [SP] and [TAB] are specializations of [empty] 
    // that always match on input. Used in the grammar to specify how output should be formatted when unparsed. 

    // [NL], a newline in the output
    symbolIndex = symbol_enterSymbol (NL_T, treeKind_empty);

    // [FL] ("Fresh Line"), a newline in the output unless it is already on a new line
    symbolIndex = symbol_enterSymbol (FL_T, treeKind_empty);

    // [IN], indent all following output lines by the default (4) or user-defined tab width
    symbolIndex = symbol_enterSymbol (IN_T, treeKind_empty);

    // [EX], un-indent all following output lines by the default (4) or user-defined tab width
    symbolIndex = symbol_enterSymbol (EX_T, treeKind_empty);

    // [SP], force a space in the output
    symbolIndex = symbol_enterSymbol (SP_T, treeKind_empty);

    // [TAB], add spaces to the next default (4) or user-defined tab stop multiple in the output
    symbolIndex = symbol_enterSymbol (TAB_T, treeKind_empty);

    // [TAB_NN], [IN_NN] and [EX_NN] are also allowed, where NN are digits, 
    // specifying custom columns or numbers of characters to tab or indent.
    // These are recognized as undefined symbols and added to the grammar symbol table as used.
    // See "custom formatting nonterminals" in makeGrammarTree below for details

    // [SPOFF] and [SPON] allow the grammar to specify unspaced sequences of unparsed tokens in output

    // [SPOFF], turn off all default and explicit output spacing
    symbolIndex = symbol_enterSymbol (SPOFF_T, treeKind_empty);

    // [SPON], turn on all default and explicit output spacing
    symbolIndex = symbol_enterSymbol (SPON_T, treeKind_empty);

    // Attributes, for adding contextual information to the parse tree
    // [attr X] is like [opt X] except that the X does not appear in the output

    // [attr X], allow for an attribute [X] at this point 
    // Represented internally using this symbol, [TXL_ATTR_]
    symbolIndex = symbol_enterSymbol (ATTR_T, treeKind_empty);

    // Backup limiters, for tuning difficult grammars

    // [KEEP], permanently commit the parse to this point (backup to [KEEP] is a syntax error)
    symbolIndex = symbol_enterSymbol (KEEP_T, treeKind_empty);

    // [!] or [FENCE], prevent backtracking before this point (backup to [!] fails the parent nonterminal) 
    // Represented internally by this symbol, [FENCE]
    symbolIndex = symbol_enterSymbol (FENCE_T, treeKind_empty);

    // Lookahead indicators, for tuning difficult parsers

    // [see X], require that the lookahead begins with an [X]
    // Represented internally using this symbol, [TXL_SEE_]
    symbolIndex = symbol_enterSymbol (SEE_T, treeKind_empty);

    // [not X], require that the lookahead does not begin with an [X]
    // Represented internally using this symbol, [TXL_NOT_]
    symbolIndex = symbol_enterSymbol (NOT_T, treeKind_empty);

    // [any], the universal nonterminal, an item of any default or user-defined nonterminal type 
    // (used in patterns and rule parameters only)
    symbolIndex = symbol_enterSymbol (any_T, treeKind_empty);
}

// Grammar analyzer
#include "analyze.h"

void defineCompiler_makeGrammarTree (const treePT txlParseTreeTP, treePT *inputGrammarTreeTP)
{
    // Begin by entering all the predefined nonterminals in the defined symbol table
    defineCompiler_setUpBuiltins ();

    // The type of the TXL predefined global TXLargs [repeat stringlit], always needed
    treePT repeat_0_stringlit_TP, repeat_1_stringlit_TP;
    defineCompiler_processRepeat (stringlit_T, &(repeat_0_stringlit_TP), &(repeat_1_stringlit_TP));

    // Process the nonterminal define statements of the input language grammar
    treePT statementsLeftTP = txltree_program_statementsTP (txlParseTreeTP);

    while (true) {
        // We're done when we've looked at every statement in the TXL program
        if (tree_plural_emptyP (statementsLeftTP)) break;

        // What kind of statement (define, rule, function) is it?
        treePT statementTP = txltree_statement_keyDefRuleTP (tree_plural_firstTP (statementsLeftTP));
        string statementKind;
        stringcpy (statementKind, *ident_idents[tree_trees[statementTP].name]);

        if (stringcmp (statementKind, "TXL_defineStatement_") == 0) {
            // If it's a nonterminal define statement, process it
            defineCompiler_processDefine (statementTP);
        } else {
            // If it's a rule or function statement, it may use nonterminal types for which there is no define,
            // e.g., [opt X], [repeat X], [list X]
            defineCompiler_processRuleImplicitTypes (statementTP);
        }

        // On to the next statement
        statementsLeftTP = tree_plural_restTP (statementsLeftTP);
    }

    // We've processed all the statements of the TXL program -
    // make sure that there is a definition for every nonterminal type in the grammar symbol table
    int errorcount = 0;

    for (int i = 1; i <= symbol_nSymbols; i++) {
        if (tree_trees[symbol_symbols[i]].kind == treeKind_undefined) {
            string undefinedName;
            stringcpy (undefinedName, *ident_idents[tree_trees[symbol_symbols[i]].name]);

            // The undefined nonterminal may be one of our custom formatting nonterminals
            // [TAB_NN], [IN_NN], [EX_NN] - if so, add a definition for it to the grammar symbol table
            string temp;

            if ((stringlen (undefinedName) >= 4) 
                    && (((substring (temp, undefinedName, 1, 4), (stringcmp (temp, "TAB_") == 0)) 
                          || ((substring (temp, undefinedName, 1, 3), stringcmp (temp, "IN_") == 0))
                          || ((substring (temp, undefinedName, 1, 3), stringcmp (temp, "EX_") == 0))))) {
                // Create custom output formatting symbol
                ident_install (undefinedName, treeKind_id);
                tree_setKind (symbol_symbols[i], treeKind_empty);

            } else {
                // Otherwise, it's a grammar symbol that's used but not defined
                string message;
                stringprintf (message, "[%s] has not been defined", undefinedName);
                error ("", message, DEFERRED, 218);
                errorcount += 1;
            }
        }
    }

    // Undefined nonterminal grammar symbols are always fatal
    if (errorcount != 0) {
        throw (QUIT);
    }

    // [push X] / [pop X] token matching only applies to token nonterminals
    // Check each one to be sure
    for (int i = 1; i <= symbol_nSymbols; i++) {
        if ((tree_trees[symbol_symbols[i]].kind == treeKind_push) 
                || (tree_trees[symbol_symbols[i]].kind == treeKind_pop)) {
            if (tree_trees[tree_kid1TP (symbol_symbols[i])].kind < firstLeafKind) {
                error ("", "[push] / [pop] target must be token type", DEFERRED, 223);
                errorcount += 1;
            }
        }
    }

    // Non-token [push/pop] errors are fatal
    if (errorcount != 0) {
        throw (QUIT);
    }

    // Normalize left recursive defines
    int nSymbols = symbol_nSymbols;     // C problem - original changes as refactoring progresses!
    for (int i = 1; i <= nSymbols; i++) {
        if (defineCompiler_isLeftRecursiveDefine (symbol_symbols[i])) {
            defineCompiler_refactorLeftRecursiveDefine (symbol_symbols[i]);
        }
    }

    // identify the root production [program]
    const tokenT programT = ident_install ("program", treeKind_id);
    const int programIndex = symbol_lookupSymbol (programT);

    if (programIndex == NOT_FOUND) {
        error ("", "[program] has not been defined", FATAL, 219);
    }

    *inputGrammarTreeTP = symbol_symbols[programIndex];

    // Analyze the grammar for serious ambiguities
    if (options_option[analyze_p]) {
        error ("", "Analyzing the input language grammar (this may take a while)", INFORMATION, 222);

        analyzeGrammar_initialize ();

        for (int i = 1; i <= symbol_nSymbols; i++) {
            analyzeGrammar_checkAdjacentCombinatorialAmbiguity (symbol_symbols[i], *inputGrammarTreeTP);
            analyzeGrammar_checkEmbeddedCombinatorialAmbiguity (symbol_symbols[i], *inputGrammarTreeTP);
            analyzeGrammar_checkRepeatEmptyAmbiguity (symbol_symbols[i], *inputGrammarTreeTP);
            analyzeGrammar_checkHiddenLeftRecursionAmbiguity (symbol_symbols[i], *inputGrammarTreeTP);
        }
    }
}

// Intialization
void defineCompiler (void) {
    analyzeGrammar ();
}
